// https://leetcode-cn.com/problems/partition-equal-subset-sum/
// 416. Partition Equal Subset Sum
// Given a non-empty array nums containing only positive integers,
// find if the array can be partitioned into two subsets such that the sum
// of elements in both subsets is equal
function canPartition(nums: number[]): boolean {
    const n = nums.length;
    if (n <= 1) return false;
    const sum = nums.reduce((a, b) => a + b);
    if (sum & 1) return false;
    const target = sum >> 1;
    if (Math.max(...nums) > target) return false;

    const dp = new Array(n)
        .fill(0)
        .map(() => new Array(target + 1).fill(false));
    for (let i = 0; i < n; i++) {
        dp[i][0] = true;
    }
    dp[0][nums[0]] = true;

    for (let i = 1; i < n; i++) {
        const num = nums[i];
        for (let j = 0; j <= target; j++) {
            if (num < j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n - 1][target];
}
